#define _CRT_SECURE_NO_WARNINGS 1

/*
        合并两个有序链表
*/

typedef struct ListNode ListNode;//避免因为类型名长而对其进行重命名
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
    //有空链表
    if (list1 == NULL)
    {
        return list2;
    }
    if (list2 == NULL)
    {
        return list1;
    }
    //无空链表
    //创建新链表，遍历两链表
    ListNode* newlist = (ListNode*)malloc(sizeof(ListNode));
    ListNode* newtail = newlist;

    while (list1 && list2)//这两个链表只要有一个走到了NULL，就说明为NULL的链表已经全部尾插完了
    {
        if (list1->val <= list2->val)
        {
            newtail->next = list1;
            newtail = newtail->next;
            //尾插完后，遍历下一个节点
            list1 = list1->next;
        }
        else
        {
            newtail->next = list2;
            newtail = newtail->next;
            //尾插完后遍历下一个节点
            list2 = list2->next;
        }
    }
    //跳出循环，说明有一个链表已经遍历完了，只需将另一个链表的剩余元素尾插到新链表
    if (list1 == NULL)
    {
        //list1遍历完了，将list2尾插到新链表中
        newtail->next = list2;
    }
    else
    {
        //list2遍历完了，将list1尾插到新链表中
        newtail->next = list1;
    }
    ListNode* ret = newlist->next;
    free(newlist);
    newlist = NULL;
    return ret;
}


/*
        //分割链表
*/

typedef struct ListNode ListNode;
struct ListNode* partition(struct ListNode* head, int x)
{
    //已知链表为空，直接返回NULL
    if (head == NULL)
    {
        return NULL;
    }
    //已知链表不为空
    //创建两个新链表，为了避免重复代码，可以利用哨兵位
    ListNode* little = (ListNode*)malloc(sizeof(ListNode));
    ListNode* littletail = little;
    ListNode* big = (ListNode*)malloc(sizeof(ListNode));
    ListNode* bigtail = big;
    //遍历原链表
    while (head)
    {
        if (head->val < x)
        {
            //小于x，将节点尾插little中
            littletail->next = head;
            littletail = littletail->next;
        }
        else
        {
            //大于等于x，将该节点尾插到big中
            bigtail->next = head;
            bigtail = bigtail->next;
        }
        //遍历下一个节点
        head = head->next;
    }
    //退出循环说明已经遍历完了原链表
    //修改bigtail指向，否则会陷入死循环
    bigtail->next = NULL;

    //连接大小链表
    //因为这两个链表都是带头链表，所以连接时要指向头结点的下一个节点
    littletail->next = big->next;

    return little->next;
}